一.概念
对于一段区间求最优解,且该区间可以分为几个小区间的最优解合并(最优子结构)。
二.基本思路
从小到大枚举区间长度,用小区间合并大区间。
代码实现也很简单:
for( int len = 1 ; len <= n ; len ++ ) //枚举长度
for( int l = 1 ; l + len - 1 <= n ; l ++ ) { //枚举当前区间左端点
int r = l + len - 1; //算出右端点
for( int k = l ; k < r ; k ++ ) { //枚举分割点
}
}
三.例题
1.P1880 [NOI1995]石子合并
这是一道区间的经典入门题板题。
因为是一个环状,所以我们先破环为链。
设 表示合并 到 这个区间内的石子的最小/最大得分。
那么有:
最后还原为环,答案为
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 200;
int n , a[ MAXN + 5 ] , sum[ MAXN + 5 ];
int dp[ 2 ][ MAXN + 5 ][ MAXN + 5 ];
int main( ) {
scanf("%d",&n);
memset( dp[ 0 ] , 0x3f , sizeof( dp[ 0 ] ) );
memset( dp[ 1 ] , 0 , sizeof( dp[ 1 ] ) );
for( int i = 1 ; i <= n ; i ++ ) {
scanf("%d",&a[ i ]);
sum[ i ] = sum[ i - 1 ] + a[ i ];
dp[ 0 ][ i ][ i ] = dp[ 1 ][ i ][ i ] = 0;
}
for( int i = n + 1 ; i <= 2 * n ; i ++ ) {
a[ i ] = a[ i - n ];
sum[ i ] = sum[ i - 1 ] + a[ i ];
dp[ 0 ][ i ][ i ] = dp[ 1 ][ i ][ i ] = 0;
}
for( int len = 1 ; len <= n ; len ++ )
for( int l = 1 ; l + len - 1 <= 2 * n ; l ++ ) {
int r = l + len - 1;
for( int k = l ; k < r ; k ++ ) {
dp[ 0 ][ l ][ r ] = min( dp[ 0 ][ l ][ r ] , dp[ 0 ][ l ][ k ] + dp[ 0 ][ k + 1 ][ r ] + sum[ r ] - sum[ l - 1 ] );
dp[ 1 ][ l ][ r ] = max( dp[ 1 ][ l ][ r ] , dp[ 1 ][ l ][ k ] + dp[ 1 ][ k + 1 ][ r ] + sum[ r ] - sum[ l - 1 ] );
}
}
int Min = 0x3f3f3f3f , Max = 0;
for( int i = 1 ; i <= n ; i ++ ) {
Min = min( Min , dp[ 0 ][ i ][ n + i - 1 ] );
Max = max( Max , dp[ 1 ][ i ][ n + i - 1 ] );
}
printf("%d\n%d\n", Min , Max );
return 0;
}
2.P4342 [IOI1998]Polygon
首先仍然是破环为链。
设 表示将 到 的区间的数进行运算的最大值。
设 为当前的分割点 , 即需要将 和 合并。
1.当 时 , 显然有:
2.当 时 ,
特殊的 ,
但是我们忘了 可以为负数 , 两个负数相乘是可能大于两个正数相乘的。
解决方法也很简单,只需要再记录一个最小值即可。
加法转移一样,乘法转移有一点变化。记 为合并 到
区间的最小值/最大值。
最后统计最大值即可。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 100;
int n , a[ MAXN + 5 ] , dp[ 2 ][ MAXN + 5 ][ MAXN + 5 ];
char op[ MAXN + 5 ];
int Get( int l , int r , int k , int f ) {
if( f == 0 )
return min( min( dp[ 0 ][ l ][ k ] * dp[ 0 ][ k + 1 ][ r ] , dp[ 1 ][ l ][ k ] * dp[ 1 ][ k + 1 ][ r ] ) , min( dp[ 0 ][ l ][ k ] * dp[ 1 ][ k + 1 ][ r ] , dp[ 1 ][ l ][ k ] * dp[ 0 ][ k + 1 ][ r ] ) );
else
return max( max( dp[ 0 ][ l ][ k ] * dp[ 0 ][ k + 1 ][ r ] , dp[ 1 ][ l ][ k ] * dp[ 1 ][ k + 1 ][ r ] ) , max( dp[ 0 ][ l ][ k ] * dp[ 1 ][ k + 1 ][ r ] , dp[ 1 ][ l ][ k ] * dp[ 0 ][ k + 1 ][ r ] ) );
}
int main( ) {
scanf("%d\n",&n);
for( int i = 1 ; i <= n ; i ++ ) {
scanf("%c %d",&op[ i ],&a[ i ]) , getchar( );
op[ i + n ] = op[ i ] , a[ i + n ] = a[ i ];
}
memset( dp[ 0 ] , 0x3f , sizeof( dp[ 0 ] ) );
memset( dp[ 1 ] , 0xcf , sizeof( dp[ 1 ] ) );
for( int i = 1 ; i <= 2 * n ; i ++ ) dp[ 0 ][ i ][ i ] = dp[ 1 ][ i ][ i ] = a[ i ];
for( int len = 1 ; len <= n ; len ++ )
for( int l = 1 ; l + len - 1 <= 2 * n ; l ++ ) {
int r = l + len - 1;
for( int k = l ; k < r ; k ++ ) {
if( op[ k + 1 ] == 't' ) {
dp[ 0 ][ l ][ r ] = min( dp[ 0 ][ l ][ r ] , dp[ 0 ][ l ][ k ] + dp[ 0 ][ k + 1 ][ r ] );
dp[ 1 ][ l ][ r ] = max( dp[ 1 ][ l ][ r ] , dp[ 1 ][ l ][ k ] + dp[ 1 ][ k + 1 ][ r ] );
}
else {
dp[ 0 ][ l ][ r ] = min( dp[ 0 ][ l ][ r ] , Get( l , r , k , 0 ) );
dp[ 1 ][ l ][ r ] = max( dp[ 1 ][ l ][ r ] , Get( l , r , k , 1 ) );
}
}
}
int Ans = 0;
for( int i = 1 ; i <= n ; i ++ )
Ans = max( Ans , dp[ 1 ][ i ][ n + i - 1 ] );
printf("%d\n", Ans );
for( int i = 1 ; i <= n ; i ++ )
if( dp[ 1 ][ i ][ n + i - 1 ] == Ans ) printf("%d ",i);
return 0;
}
3.CF149D Coloring Brackets
为了方便讨论,先处理出每个括号对应的匹配,记为 。
表示现在处理的区间为 到 并且是一个匹配序列,左端点红/蓝/不染,右端点红/蓝/不染,那么有三种情况:
1.
即匹配的括号是相邻的,形如 ,那么只需要将任意端点染一个颜色,只有一种方案。
2.
即合法序列的两端是匹配的,去掉两端后的区间显然也是合法的,所以我们先递归处理 。
然后保证 和 的颜色不同 , 和 的颜色不同,进行转移即可。
3.
即合法序列由两部分构成: 到 和 到 ,同样先递归处理。
然后枚举分成的两部分的端点颜色,保证左区间的右端点和右区间的左端点颜色不同(但可以都不染),就可以转移了。
#include <stack>
#include <cstdio>
#include <cstring>
using namespace std;
#define Mod 1000000007
const int MAXN = 700;
int n , p[ MAXN + 5 ] , dp[ MAXN + 5 ][ MAXN + 5 ][ 3 ][ 3 ];
char str[ MAXN + 5 ];
stack< int > s;
void dfs( int l , int r ) {
if( r == l + 1 ) {
dp[ l ][ r ][ 0 ][ 1 ] = dp[ l ][ r ][ 1 ][ 0 ] = 1;
dp[ l ][ r ][ 0 ][ 2 ] = dp[ l ][ r ][ 2 ][ 0 ] = 1;
}
else if( p[ l ] == r ) {
dfs( l + 1 , r - 1 );
for( int l1 = 0 ; l1 <= 2 ; l1 ++ )
for( int r1 = 0 ; r1 <= 2 ; r1 ++ ) {
if( l1 != 1 ) dp[ l ][ r ][ 1 ][ 0 ] = ( dp[ l ][ r ][ 1 ][ 0 ] + dp[ l + 1 ][ r - 1 ][ l1 ][ r1 ] ) % Mod;
if( l1 != 2 ) dp[ l ][ r ][ 2 ][ 0 ] = ( dp[ l ][ r ][ 2 ][ 0 ] + dp[ l + 1 ][ r - 1 ][ l1 ][ r1 ] ) % Mod;
if( r1 != 1 ) dp[ l ][ r ][ 0 ][ 1 ] = ( dp[ l ][ r ][ 0 ][ 1 ] + dp[ l + 1 ][ r - 1 ][ l1 ][ r1 ] ) % Mod;
if( r1 != 2 ) dp[ l ][ r ][ 0 ][ 2 ] = ( dp[ l ][ r ][ 0 ][ 2 ] + dp[ l + 1 ][ r - 1 ][ l1 ][ r1 ] ) % Mod;
}
}
else {
dfs( l , p[ l ] ) , dfs( p[ l ] + 1 , r );
for( int l1 = 0 ; l1 <= 2 ; l1 ++ )
for( int r1 = 0 ; r1 <= 2 ; r1 ++ )
for( int l2 = 0 ; l2 <= 2 ; l2 ++ )
for( int r2 = 0 ; r2 <= 2 ; r2 ++ )
if( r1 == 0 || r1 != l2 )
dp[ l ][ r ][ l1 ][ r2 ] = ( dp[ l ][ r ][ l1 ][ r2 ] + 1ll * dp[ l ][ p[ l ] ][ l1 ][ r1 ] * dp[ p[ l ] + 1 ][ r ][ l2 ][ r2 ] ) % Mod;
}
}
int main( ) {
// freopen("coloring.in","r",stdin);
// freopen("coloring.out","w",stdout);
scanf("%s", str + 1 ); n = strlen( str + 1 );
for( int i = 1 ; i <= n ; i ++ ) {
if( str[ i ] == '(' ) s.push( i );
if( str[ i ] == ')' ) {
int t = s.top(); s.pop();
p[ i ] = t , p[ t ] = i;
}
}
dfs( 1 , n );
int Ans = 0;
for( int i = 0 ; i <= 2 ; i ++ )
for( int j = 0 ; j <= 2 ; j ++ )
Ans = ( Ans + dp[ 1 ][ n ][ i ][ j ] ) % Mod;
printf("%d", Ans );
return 0;
}
4.P3736 [HAOI2016]字符合并
为了使结果更大,我们肯定会合并至无法合并为止。
记 表示 将 到 这段区间最终合并为 的最大分数。显然 的位数小于 , 考虑状压。
首先 , 其余赋为极小值避免无效转移。
区间 的套路,枚举分割点 , 且 的左边贡献 , 右边贡献 ,组合得到 由于 数字 只会由位数为 的字符串产生,所以 每次减 即可。
然后有:
最后有一种特殊情况,当区间长度恰好为 时直接合并成一个字符。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define INF 1e15
const int MAXN = 300;
int n , m , k , str[ MAXN + 5 ] , c[ MAXN + 5 ] , w[ MAXN + 5 ];
long long dp[ MAXN + 5 ][ MAXN + 5 ][ MAXN + 5 ];
int main( ) {
scanf("%d %d",&n,&k); m = 1 << k;
for( int i = 1 ; i <= n ; i ++ )
scanf("%d",&str[ i ]);
for( int i = 0 ; i < m ; i ++ )
scanf("%d %d",&c[ i ],&w[ i ]);
memset( dp , 0xcf , sizeof( dp ) );
for( int l = n ; l >= 1 ; l -- )
for( int r = l ; r <= n ; r ++ ) {
if( l == r ) {
dp[ l ][ r ][ str[ l ] ] = 0;
continue;
}
int len = ( r - l ) % ( k - 1 );
if( len == 0 ) len = k - 1;
for( int i = r - 1 ; i >= l ; i -= k - 1 )
for( int S = 0 ; S < 1 << len ; S ++ ) {
dp[ l ][ r ][ S << 1 ] = max( dp[ l ][ r ][ S << 1 ] , dp[ l ][ i ][ S ] + dp[ i + 1 ][ r ][ 0 ] );
dp[ l ][ r ][ S << 1 | 1 ] = max( dp[ l ][ r ][ S << 1 | 1 ] , dp[ l ][ i ][ S ] + dp[ i + 1 ][ r ][ 1 ] );
}
if( len == k - 1 ) {
long long tmp[ 2 ]; tmp[ 0 ] = -INF , tmp[ 1 ] = -INF;
for( int S = 0 ; S < m ; S ++ )
tmp[ c[ S ] ] = max( tmp[ c[ S ] ] , dp[ l ][ r ][ S ] + w[ S ] );
dp[ l ][ r ][ 0 ] = tmp[ 0 ] , dp[ l ][ r ][ 1 ] = tmp[ 1 ];
}
}
// for( int l = 1 ; l <= n ; l ++ )
// for( int r = l ; r <= n ; r ++ )
// for( int S = 0 ; S < m ; S ++ )
// printf("dp[%d][%d][%d]=%lld\n",l,r,S,dp[l][r][S]);
long long Ans = -INF;
for( int i = 0 ; i < m ; i ++ )
Ans = max( Ans , dp[ 1 ][ n ][ i ] );
printf("%lld", Ans );
return 0;
}
5.P4302 [SCOI2003]字符串折叠
表示将 折叠后的最小长度。
特别的,。
那么有两种转移:
1.枚举划分点,将两区间长度相加。
2.将整个区间折叠,同样枚举划分点,判断是否能以该划分点折叠。
时间复杂度 。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 100;
int n , dp[ MAXN + 5 ][ MAXN + 5 ];
char str[ MAXN + 5 ];
bool check( int l , int r , int len ) {
for( int i = l ; i <= l + len - 1 ; i ++ )
for( int j = i ; j <= r ; j += len )
if( str[ i ] != str[ j ] ) return 0;
return 1;
}
int chk( int x ) {
int d = 0;
for( ; x ; x /= 10 , d ++ );
return d;
}
int main( ) {
scanf("%s", str );
n = strlen( str );
memset( dp , 0x3f , sizeof( dp ) );
for( int i = 0 ; i < n ; i ++ ) dp[ i ][ i ] = 1;
for( int len = 2 ; len <= n ; len ++ )
for( int l = 0 , r ; l + len - 1 < n ; l ++ ) {
r = l + len - 1;
for( int k = l ; k < r ; k ++ )
dp[ l ][ r ] = min( dp[ l ][ r ] , dp[ l ][ k ] + dp[ k + 1 ][ r ] );
for( int k = l ; k < r ; k ++ ) {
int flen = k - l + 1;
if( len % flen == 0 && check( l , r , flen ) )
dp[ l ][ r ] = min( dp[ l ][ r ] , chk( len / flen ) + 1 + dp[ l ][ k ] + 1 );
}
}
printf("%d\n", dp[ 0 ][ n - 1 ] );
return 0;
}